package 面试题17_24_最大子矩阵;

import java.util.Arrays;

public class Main {
}

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int max = Integer.MIN_VALUE;
        int[] dp = new int[m];
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        for(int str = 0; str < n ; str++ ) {
            Arrays.fill(dp, 0);
            for(int end = str; end<n;end++) {
                for(int l = 0, r = 0, pre = Integer.MIN_VALUE; r<m; r++) {
                    dp[r] += matrix[end][r];
                    if(pre>=0) {
                        pre += dp[r];
                    }else{
                        pre = dp[r];
                        l = r;
                    }
                    if(pre>max) {
                        max = pre;
                        a = str;
                        b = l;
                        c = end;
                        d = r;
                    }
                }
            }
        }
        return new int[]{a, b, c, d};
    }
}